package com.zjsru.oneDay;

import java.util.Arrays;

/**
 * 2966. 划分数组并满足最大差限制
 *
 * @Author: cookLee
 * @Date: 2025-06-18
 */
public class DivideArray {

    /**
     * 主
     * \
     * 输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
     * 输出：[[1,1,3],[3,4,5],[7,8,9]]
     * 解释：
     * 每个数组中任何两个元素之间的差小于或等于 2。
     * \
     * 输入：nums = [2,4,2,2,5,2], k = 2
     * 输出：[]
     * 解释：
     * 将 nums 划分为 2 个长度为 3 的数组的不同方式有：
     * [[2,2,2],[2,4,5]] （及其排列）
     * [[2,2,4],[2,2,5]] （及其排列）
     * 因为有四个 2，所以无论我们如何划分，都会有一个包含元素 2 和 5 的数组。因为 5 - 2 = 3 > k，条件无法被满足，所以没有合法的划分。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 4, 8, 7, 9, 3, 5, 1};
        int k = 2;
        System.out.println(Arrays.deepToString(new DivideArray().divideArray(nums, k)));
    }

    /**
     * 贪心
     *
     * @param nums nums
     * @param k    k
     * @return {@link int[][]}
     */
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        int[][] ans = new int[nums.length / 3][3];

        int len = nums.length;
        for (int i = 0; i < len; i += 3) {
            //子数组中 任意 两个元素的差必须 小于或等于 k 。
            if (nums[i + 2] - nums[i] > k) {
                return new int[0][0];
            }
            ans[i / 3][0] = nums[i];
            ans[i / 3][1] = nums[i + 1];
            ans[i / 3][2] = nums[i + 2];
        }
        return ans;
    }


}
